- transitive reduction
- мат.транзитивное сокращение
English-Russian scientific dictionary. 2008.
transitive reduction
Смотреть что такое "transitive reduction" в других словарях:
Transitive reduction — In mathematics, the transitive reduction of a binary relation R on a set X is a minimal relation R on X such that the transitive closure of R is the same as the transitive closure of R . If the transitive closure of R is antisymmetric and finite … Wikipedia
Transitive closure — In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R .For example, if X is a set of airports and xRy means there is a direct flight from airport x to airport y , then… … Wikipedia
Transitive relation — In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b , and b is in turn related to an element c , then a is also related to c . Transitivity is a key property of both partial order… … Wikipedia
Reduction (complexity) — Example of a reduction from a boolean satisfiability problem to a vertex cover problem. Blue vertices form a vertex cover which corresponds to truth values. In computability theory and computational complexity theory, a reduction is a… … Wikipedia
Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… … Wikipedia
Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to … Wikipedia
Many-one reduction — In computability theory and computational complexity theory, a many one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative… … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Binary relation — Relation (mathematics) redirects here. For a more general notion of relation, see Finitary relation. For a more combinatorial viewpoint, see Theory of relations. In mathematics, a binary relation on a set A is a collection of ordered pairs of… … Wikipedia
